package list
/**
 * 合并链表
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
type ListNode struct {
  Val int
  Next *ListNode
}
//合并两个有序链表
//双指针法 , l1指针小于l2指针 l1塞入新链表,并下移, 否则l2塞入,l2下移
func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	//定义一个新的链表头
	var root =&ListNode{
	}
	//操作一个副本 , 因为都是指针所以也会影响到root
	//这个副本会不停的往下移动, 如果没有这个副本直接操作root , root只会是最后一个结点
	node:=root
	//l1不为 nil 并且 l2不为nil
	for l1!=nil && l2!=nil{
		//判断两个结点值的大小 , 小的一方链表塞入新链表
		if l1.Val<l2.Val{
			node.Next=l1
			l1=l1.Next
		}else{
			node.Next=l2
			l2=l2.Next
		}
		//新链表也得往下移动 , 要不然会被覆盖
		node=node.Next
	}
	//当前面的循环 , 有一方没有到底的时候 , 那一方肯定是大的 , 把链表直接塞入新链表
	if l1!=nil{
		node.Next=l1
	}
	if l2!=nil{
		node.Next=l2
	}
	return root.Next
}
